package leetcode.hot100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

public class Solution128 {

    public static void main(String[] args) {
        int[] nums = new int[]{0,3,7,2,5,8,4,6,0,1};
        System.out.println(new Solution128().longestConsecutive(nums));
    }

    /*
     * 动态规划，用hashMap记录连续序列端点，key是端点数字，value是该连续序列长度
     * 有新的端点续上时更新左右端点value并更新最大值
     */
    public int longestConsecutive(int[] nums) {
        HashMap<Integer,Integer> hash = new HashMap<>();
        int max = 0;
        for (int num : nums) {
            if(hash.containsKey(num)) continue;
            //先找相邻长度
            int leftLen = hash.getOrDefault(num-1,0);
            int rightLen = hash.getOrDefault(num+1,0);
            //更新总长度
            int len = leftLen+rightLen+1;
            max = Math.max(max,len);
            //更新端点长度
            hash.put(num,len);
            hash.put(num-leftLen,len);
            hash.put(num+rightLen,len);
        }
        return max;
    }

    public int longestConsecutive2(int[] nums) {
        int len = nums.length;
        if(len==0) return 0;
        //排序
        Arrays.sort(nums);
        //统计
        int maxLen = 1, curMax = 1;
        for(int i=1;i<len;i++){
            if(nums[i]-nums[i-1]==1){
                curMax++;
            }else{
                maxLen = Math.max(curMax,maxLen);
                curMax = 1;
            }
        }
        return Math.max(curMax,maxLen);
    }

    public int longestConsecutive1(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();
        for (int num: nums) {
            hashSet.add(num);
        }
        int realMax = 1, curMax = 1;
        for (int num: hashSet) {
            //只有连续数字的第一个数字才会往后看有多少连续
            if(!hashSet.contains(num-1)){
                int start = num+1;
                //如果存在连续就统计
                while(hashSet.contains(start++)) curMax++;
                //更新realMax
                realMax = Math.max(realMax,curMax);
            }
        }
        return realMax;
    }
}
